package com.fr.lintcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Q825 {


    /**
     * @param N: The number of buses
     * @param route: The route of buses
     * @param A: Start bus station
     * @param B: End bus station
     * @return: Return the minimum transfer number
     */
    public int getMinTransferNumber(int N, int[][] route, int A, int B) {
		// 站点和线路的关系
		Map<Integer, Set<Integer>> routeMap = new HashMap<>();
		for (int i = 0; i < route.length; i++) {
			for (int j = 0; j < route[i].length; j++) {
				Set<Integer> line = routeMap.get(route[i][j]);
				if (line == null) {
					line = new HashSet<>();
					routeMap.put(route[i][j], line);
				}
				line.add(i);
			}
		}
		Set<Integer> sites = new HashSet<>();
		Set<Integer> lines = new HashSet<>();
		Set<Integer> tmp = routeMap.get(A);
		int count = 1;
		while (tmp != null && tmp.size() > 0) {
			Set<Integer> tmp1 = new HashSet<>();
			for (int line : tmp) {
				if (!lines.contains(line)) {
					lines.add(line);
					for (int site : route[line]) {
						if (site == B) {
							return count;
						}
						if (!sites.contains(site)) {
							sites.add(site);
							tmp1.addAll(routeMap.get(site));
						}
					}
				}
			}
			tmp1.removeAll(lines);
			tmp.clear();
			tmp.addAll(tmp1);
			count++;
		}
		return -1;
	}

}
